#include <iostream>
#include <ctime>
#include <random>
using namespace std;

int *partition(int *arr, int *left, int *right)
{
	int Key = *right;
	int *p1 = left;
	int *p2 = left - 1;
	for (; p1 != right; ++p1)
	{
		if (*p1 <= Key)
		if (++p2 != p1)
			swap(*p1, *p2);
	}
	swap(*(p2 + 1), *right);
	return p2;

}
int * Random(int *arr, int *left, int *right)
{
	srand(time(NULL));
	size_t i = rand() % (left - right);
	swap(*left, *(left + i));
	return partition(arr, left, right);
}
void QuickSort(int *arr, int *left, int *right)
{
	if (left >= right)
		return;
	int *p2 = Random(arr, left, right);
	QuickSort(arr, left, p2);
	QuickSort(arr, p2 + 1, right);
}

int main()
{
	int arr1[] = {21, 12, 3, 16, 29, 1, 42};
	QuickSort(arr1, &arr1[0], &arr1[6]);
	return 0;
}
